package com.classicalAlgorithm.LRU;


import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.LinkedList;

class Node {
    public int key, val;
    public Node next, prev;

    public Node(int k, int v) {
        this.key = k;
        this.val = v;
    }
}


class DoubleList {
    // 头尾虚节点
    private Node head, tail;

    // 链中节点元素数
    public int size;

    public DoubleList() {
        // 初始化双向链表的数据
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
        size = 0;
    }

    // 在双向链表末尾添加一个节点
    public void addLast(Node x) {
        // 链表中插入一个节点需要四步操作
        x.prev = tail.prev;
        x.next = tail;
        tail.prev.next = x;
        tail.prev = x;

        // 增加size
        size++;
    }

    // 删除链表中的x节点（x必须存在于该链表中
    public void remove(Node x) {
        x.prev.next = x.next;
        x.next.prev = x.prev;
        size++;
    }

    // 删除链表中头结点后的第一个结点
    public Node removeFirst() {
        if (head.next == tail) {
            return null;
        }
        Node first = head.next;
        remove(first);
        size--;

        return first;
    }

}


public class LRU {

}


/*
 *
 *

 *
 * */


class LRUCache01 {
    // key->Node(key, val)
    private HashMap<Integer, Node> map;
    private DoubleList cache;

    // 最大容量
    private int cap;

    // LRUCache(int capacity) 以正整数作为容量capacity 初始化 LRU 缓存
    public LRUCache01(int capacity) {
        this.cap = capacity;
        map = new HashMap<>();

        // 双向链表 头部是旧的结点
        // 新结点从尾部插入
        cache = new DoubleList();
    }


    // int get(int key) 如果关键字 key 存在于缓存中，
    // 则返回关键字的值，否则返回 -1 。
    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }

        makeRecently(key);
        return map.get(key).val;
    }

    //    void put(int key, int value)
//    如果关键字已经存在，则变更其数据值；
//    如果关键字不存在，则插入该组「关键字-值」。
//    当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，
//    从而为新的数据值留出空间。
    public void put(int key, int value) {

        if (map.containsKey(key)) {
            // 删除并提到前面
            deleteKey(key);

            addRecently(key, value);
            return;
        }

        if (cap == cache.size) {
            // 删除最久未使用的元素
            removeLeastRecently();
        }
        addRecently(key, value);

    }

    // 将某个key所在的结点提升为最近使用的
    private void makeRecently(int key) {
        Node targetNode = map.get(key);

        // 从链表中删除
        cache.remove(targetNode);

        // 插入到链表尾部
        cache.addLast(targetNode);
    }

    // 添加最近使用的元素
    private void addRecently(int key, int val) {
        Node recentNode = new Node(key, val);

        // 链表中添加
        cache.addLast(recentNode);

        // hashmap中添加
        map.put(key, recentNode);
    }

    // 删除某一个key
    private void deleteKey(int key) {
        Node x = map.get(key);

        // 在链表中删除
        cache.remove(x);

        // 在hashmap中删除
        map.remove(key);
    }

    // 删除最久没使用的key
    private void removeLeastRecently() {
        // 获取到这个被删除的结点
        Node deleteNode = cache.removeFirst();

        // 别忘了在map中也删除一下
        // 从map中删除这个key
        map.remove(deleteNode.key);
    }
}


class LRUCache {
    //    key->Node(key, val)
    private HashMap<Integer, Node> map;
    private LinkedList<Node> cache;

    // 最大容量
    private int cap;

    // LRUCache(int capacity) 以正整数作为容量capacity 初始化 LRU 缓存
    public LRUCache(int capacity) {
        this.cap = capacity;
        map = new HashMap<>();

        // 双向链表 头部是旧的结点
        // 新结点从尾部插入
        cache = new LinkedList<>();
    }


    // int get(int key) 如果关键字 key 存在于缓存中，
    // 则返回关键字的值，否则返回 -1 。
    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }

        makeRecently(key);
        return map.get(key).val;
    }

    //    void put(int key, int value)
//    如果关键字已经存在，则变更其数据值；
//    如果关键字不存在，则插入该组「关键字-值」。
//    当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，
//    从而为新的数据值留出空间。
    public void put(int key, int value) {

        if (map.containsKey(key)) {
            // 删除并提到前面
            deleteKey(key);

            addRecently(key, value);
            return;
        }

        // 如果容量满了，淘汰最久未使用的那个
        if (cap == cache.size()) {
            // 删除最久未使用的元素
            removeLeastRecently();
        }
        // 添加元素
        addRecently(key, value);
    }

    // 将某个key所在的结点提升为最近使用的
    private void makeRecently(int key) {
        Node targetNode = map.get(key);

        // 从链表中删除
        cache.remove(targetNode);

        // 插入到链表尾部
        cache.addLast(targetNode);
    }

    // 添加最近使用的元素
    private void addRecently(int key, int val) {
        Node recentNode = new Node(key, val);

        // 链表中添加
        cache.addLast(recentNode);

        // hashmap中添加
        map.put(key, recentNode);
    }

    // 删除某一个key
    private void deleteKey(int key) {
        Node x = map.get(key);

        // 在链表中删除
        cache.remove(x);

        // 在hashmap中删除
        map.remove(key);
    }

    // 删除最久没使用的key
    private void removeLeastRecently() {
        // 获取到这个被删除的结点
        Node deleteNode = cache.removeFirst();

        // 从map中删除这个key
        map.remove(deleteNode.key);
    }
}


class LRUCache02 {
    //    key->Node(key, val)
    private LinkedHashMap<Integer, Integer> cache;

    // 最大容量
    private int cap;

    // LRUCache(int capacity) 以正整数作为容量capacity 初始化 LRU 缓存
    public LRUCache02(int capacity) {
        this.cap = capacity;
        cache = new LinkedHashMap<>();
    }


    // int get(int key) 如果关键字 key 存在于缓存中，
    // 则返回关键字的值，否则返回 -1 。
    public int get(int key) {
        if(!cache.containsKey(key)){
            return -1;
        }

        int x = cache.get(key);

        // 并把它变成最近使用的
        makeRecently(key);

        return x;
    }

    //    void put(int key, int value)
//    如果关键字已经存在，则变更其数据值；
//    如果关键字不存在，则插入该组「关键字-值」。
//    当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，
//    从而为新的数据值留出空间。
    public void put(int key, int value) {
        if(cache.containsKey(key)){
            // 先删除原来的数据，再重新加进去
            cache.remove(key);
            cache.put(key, value);
            return;
        }

        // 先判断有没有满
        if(cache.size() == cap){
            // 先删除掉最旧的
            // 链表头部就是最旧的
            int oldKey = cache.keySet().iterator().next();
            cache.remove(oldKey);
        }

        cache.put(key, value);

    }

    // 将某个key所在的结点提升为最近使用的
    private void makeRecently(int key) {
        int val = cache.get(key);

        cache.remove(val);

        // 重新插入到队尾
        cache.put(key, val);
    }
}